今天要看的是狀態機 DP。在每個時間節點都有多種可能的狀態，這些狀態之間會有一些關聯和限制。狀態機 DP 的目的就是定義清楚這些狀態間的轉移，然後總結出最後一個時間節點的情形。

用打家劫舍的問題來當例子比較好懂。有一排連續的房子，小偷可以隨機選擇要偷竊的房屋，但是不能偷連續兩間，否則會觸發警報。而偷竊每間房子的獲益不太相同，因此會用 DP 來計算最高受益。一間房子有被偷和沒被偷兩種狀態，如果房屋 n 被偷，則房屋 n-1 一定沒被偷；而如果房屋 n 沒被偷，則房屋 n-1 可以是任一種狀態。運用這樣的規律去寫出 DP 轉移方程，然後就能用矩陣運算來解題。

而 552. Student Attendance Record II 這題也是類似，可以分別計算正常出席、遲到一次、遲到兩次這三種狀態的可能情形。而缺席則稍微複雜一點，這裡是將缺席的 case 獨立計算，去統計在不同時間節點時缺席的可能數（會是前後的方案數相乘），然後就能得到最後的結果了。

class Solution:
    def checkRecord(self, n: int) -> int:
        if n == 1:
            return 3
        elif n == 2:
            return 8

        arr = [[0]*4 for _ in range(n+1)]
        arr[1] = [1,1,0,2]

        mod = 10**9+7

        for i in range(2, n+1):
            arr[i][0] = arr[i-1][3] % mod
            arr[i][1] = arr[i-1][0] % mod
            arr[i][2] = arr[i-1][1] % mod
            arr[i][3] = (arr[i][0]+arr[i][1]+arr[i][2]) % mod
        
        ans = arr[-1][-1]
        ans += arr[-2][-1]*2
        ans %= mod

        for i in range(2, n):
            tmp = arr[i-1][-1] * arr[n-i][-1] % mod
            ans += tmp
        
        return ans % mod

• 狀態機 DP
  • 552. Student Attendance Record II

Total Count: 16